{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### [881\\. Boats to Save People](https://leetcode.com/problems/boats-to-save-people/)\n", "\n", "Difficulty: **Medium** \n", "\n", "Related Topics: [Two Pointers](https://leetcode.com/tag/two-pointers/), [Greedy](https://leetcode.com/tag/greedy/)\n", "\n", "\n", "The `i`-th person has weight `people[i]`, and each boat can carry a maximum weight of `limit`.\n", "\n", "Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most `limit`.\n", "\n", "Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)\n", "\n", "\n", "**Example 1:**\n", "\n", "```\n", "Input: people = [1,2], limit = 3\n", "Output: 1\n", "Explanation: 1 boat (1, 2)\n", "```\n", "\n", "\n", "**Example 2:**\n", "\n", "```\n", "Input: people = [3,2,2,1], limit = 3\n", "Output: 3\n", "Explanation: 3 boats (1, 2), (2) and (3)\n", "```\n", "\n", "\n", "**Example 3:**\n", "\n", "```\n", "Input: people = [3,5,3,4], limit = 5\n", "Output: 4\n", "Explanation: 4 boats (3), (3), (4), (5)\n", "```\n", "\n", "**Note**:\n", "\n", "* `1 <= people.length <= 50000`\n", "* `1 <= people[i] <= limit <= 30000`\n", "\n", "\n", "#### Solution\n", "\n", "Language: **Java**\n", "\n", "```java\n", "class Solution {\n", "    public int numRescueBoats(int[] people, int limit) {\n", "        \n", "   }\n", "}\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n", "5\n", "3\n", "4\n" ] } ], "source": [ "class Solution {\n", " public int numRescueBoats(int[] people, int limit) {\n", " for (int i = 0; i < people.length; i++) {\n", " System.out.println(people[i]);\n", " }\n", " return 0;\n", " }\n", "\n", " public static void main(String[] args) {\n", " int[] people = {3,5,3,4};\n", " int limit = 5;\n", " Solution s = new Solution();\n", " s.numRescueBoats(people, limit);\n", " }\n", "}\n", "\n", "String[] args = {};\n", "Solution.main(args);" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In Java, arrays can’t grow once they have been created; so, to add an element, you need to:\n", "\n", "1. Create a new, larger array.\n", "\n", "2. Copy over the content of the original array.\n", "\n", "3. Insert the new element at the end.\n", "\n", "> Thank to god that we have vectors" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "https://leetcode.com/problems/boats-to-save-people/\n", "\n", "\n", "\n", "Time Limit Exceeded\n", "\n", "\n", "\n", "```java\n", "import java.util.Arrays;\n", "import java.util.Collections;\n", "import java.util.Vector;\n", "\n", "class Solution {\n", " Vector used_index = new Vector();\n", "\n", " private Boolean is_used(Integer e) {\n", " return this.used_index.contains(e);\n", " }\n", "\n", " public int numRescueBoats(int[] people, int limit_) {\n", " // java is funny, the int and Integer are different types\n", " Integer[] arr = new Integer[people.length];\n", " for (int i = 0; i < people.length; i++) {\n", " arr[i] = Integer.valueOf(people[i]);\n", " }\n", " Integer limit = Integer.valueOf(limit_);\n", "\n", " // the sort function is also funny, it can only take Integer array as // argument（parameter）\n", " Arrays.sort(arr, Collections.reverseOrder());\n", "\n", " int boats = 0;\n", " Integer target = 0;\n", " for (int i=0; i < arr.length; ++i) {\n", " Integer e = arr[i];\n", "\n", " if (this.is_used(i)) {\n", " continue;\n", " }\n", "\n", " if (e <= limit) {\n", " this.used_index.add(i);\n", " target = limit - e;\n", " for (int j = i+ 1; j < arr.length; ++j) {\n", " if (this.is_used(j)) {\n", " continue;\n", " }\n", " e = arr[j];\n", " if (e <= target) {\n", " this.used_index.add(j);\n", " break;\n", " }\n", " }\n", " boats += 1;\n", " }\n", " }\n", "\n", " return boats;\n", " }\n", "\n", " public static void main(String[] args) {\n", " int[] people = { 3, 2, 2, 1 };\n", " int limit = 3;\n", " Solution s = new Solution();\n", " int r = s.numRescueBoats(people, limit);\n", " System.out.println(r);\n", " }\n", "}\n", "```\n", "\n", "Time out\n", "\n", "It's just an attempt to convert python solution to java" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Java", "language": "java", "name": "java" }, "language_info": { "codemirror_mode": "java", "file_extension": ".jshell", "mimetype": "text/x-java-source", "name": "Java", "pygments_lexer": "java", "version": "11.0.8-internal+0-adhoc..src" } }, "nbformat": 4, "nbformat_minor": 4 }